# mergesort.S 							
# 								
# - Argumentos:							
# 	* a0: dirección inicial del arreglo a ordenar.		
#	* a1: tamaño del arreglo.				
#								
# - No devuelve ningún valor de retorno. 			
#								
# - Stack frame: 56 bytes					
#	* Los 32 superiores se usan para el SRA + padding.	
#	* Los 24 inferiores son espacio reservado para 	
#	  el ABA (5 argumentos + padding).										


#include <mips/regdef.h>
#include <sys/syscall.h>

#define 	SSIZE 	(56)

#define		O_RA 	(48)
#define		O_FP 	(44)
#define		O_GP	(40)

#define 	O_S3 	(36)
#define 	O_S2 	(32)
#define 	O_S1 	(28)
#define 	O_S0 	(24)

#define 	O_ARG0	(SSIZE)
#define 	O_ARG1	((SSIZE) + 4)


#void mergeSort(char* entrada, int tamanioEntrada)

	.text
	.align 	2
	.globl	merge_sort
	.ent	merge_sort

merge_sort:
   	.frame $fp, SSIZE, ra
   	.set noreorder
   	.cpload t9
   	.set reorder     
	
		subu	sp,sp,SSIZE 		#crea el stack.

		sw 	s0, O_S0(sp)
		sw 	s1, O_S1(sp)
		sw 	s2, O_S2(sp)
		sw 	s3, O_S3(sp)

		#sw	gp, O_GP(sp)
		.cprestore O_GP
		sw	$fp, O_FP(sp)
		sw	ra, O_RA(sp) 	

		move	$fp, sp

		sw	a0, O_ARG0($fp)
		sw	a1, O_ARG1($fp)


		lw 	t0, O_ARG1($fp) 	#t0 es tamanioEntrada
		addi 	t1, t0, -1
		
		beq 	t1, zero, SALIDA 	#if (tamanioEntrada > 1) sigue, si no, destruye el stack y sale.

		srl 	s0, t0, 1 		#s0 es tamanioBuffer1 = tamanioEntrada/2
		subu 	s1, t0, s0		#s1 es tamanioBuffer2 = tamanioEntrada - tamanioBuffer1

						
		la 	t9, mymalloc 		#llama a mymalloc para buffer1 y buffer2.
		move	a0, s0
		jalr	t9
		move 	s2, v0			#s2 es la dirección inicial de buffer1.
		
		beqz 	v0, BAD_ALLOC
		
		la 	t9, mymalloc
		move 	a0, s1
		jalr 	t9
		move 	s3, v0 			#s3 es la dirección inicial de buffer2.

		beqz 	v0, BAD_ALLOC
						#fin de los malloc.
		
						#llamadas a memcpy para llenar los buffers con el contenido del array.
		move 	a0, s2
		lw 	a1, O_ARG0($fp) 	#carga la dirección inicial del array (a0) en a1.
		move 	a2, s0		
		la 	t9, mymemcpy
		jalr 	t9

		move 	a0, s3
		lw 	a1, O_ARG0($fp)
		addu 	a1, a1, s0 		#dirección donde comienza la 2da mitad del array.
		move 	a2, s1
		la 	t9, mymemcpy
		jalr 	t9
						#fin de los memcpy.

		move 	a0, s2 			#llamadas recursivas a merge_sort para buffer1 y buffer2
		move 	a1, s0
		la 	t9, merge_sort
		jalr 	t9
		
		move 	a0, s3
		move 	a1, s1
		la 	t9, merge_sort
		jalr 	t9
						#fin de los merge sort.

		move 	a0, s2 			#llamada a merge_buffers
		move 	a1, s0
		move 	a2, s3
		move 	a3, s1
		lw 	t8, O_ARG0($fp)
		sw 	t8, 16($fp) 		#el 5to argumento lo pasa por stack
		la 	t9, merge_buffers
		jalr 	t9

		move 	a0, s2			#llama a myfree para buffer1 y buffer2
		la 	t9, myfree
		jalr 	t9

		move 	a0, s3
		la 	t9, myfree
		jalr 	t9 			#fin de los free.

		li 	v0, 1
	
UNWIND: 	lw 	s0, O_S0($fp)		#destruye el stack
		lw 	s1, O_S1($fp)
		lw 	s2, O_S2($fp)
		lw 	s3, O_S3($fp)

		move 	sp, $fp
		lw	gp, O_GP($fp)
		lw 	ra, O_RA($fp)
		lw	$fp, O_FP($fp)
		
		addiu 	sp, sp, SSIZE
		jr 	ra

SALIDA:		li 	v0, 1
		b 	UNWIND
		
BAD_ALLOC: 	li 	v0, 0 			#el 0 indica que el algoritmo no pudo finalizar correctamente
		b 	UNWIND

	.end 	merge_sort
